﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TrafficLab
{
    class Process
    {
        private List<Intersection> NetworkIntersections = new List<Intersection>();
        private List<RoadSection> NetworkRoads = new List<RoadSection>();

        #region Simulate Produce map Part.

        // Simulate produce the network.

        private void GetMapData(List<Intersection> NetworkIntersections, List<RoadSection> NetworkRoads)
        {
            SimulateProduce(NetworkIntersections, NetworkRoads);
        }

        private void SimulateProduce(List<Intersection> NetworkIntersections, List<RoadSection> NetworkRoads)
        {
            // Set these two lists.

            //List<Intersection> Network = new List<Intersection>();
            //List<RoadSection> roads = new List<RoadSection>();

            // 10 * 10 - 4 = 77

            // First process objects.
            // Then relate objects.
            int nInterSize = 10 * 10;

            for (int i = 1; i <= nInterSize; i++)
            {
                // remove 4 node.
                if ((1 == i) || (91 == i) || (10 == i) || (100 == i))
                {
                    continue;
                }

                String eachID = GetInterID(i);

                Intersection eachInter = new Intersection(eachID, i);

                NetworkIntersections.Add(eachInter);
            }

            int iNetSize = NetworkIntersections.Count;
            for (int i = 0; i < iNetSize; i++)
            {
                // Produce road.
                Intersection eachInter = NetworkIntersections[i];
                ProduceRoads(eachInter, NetworkRoads, NetworkIntersections);
            }

            // Random set travel time. 
            int nRoadSize = NetworkRoads.Count;
            for (int i = 0; i < nRoadSize; i++)
            {
                RoadSection road = NetworkRoads[i];

                // Random get value from 1 to 15
                Random ro = new Random(i);

                int iResult;
                int iUp = 15;
                int iDown = 1;
                iResult = ro.Next(iDown, iUp);

                road.SetTravelTime(iResult);


            }

        }

        private void ProduceRoads(
                                    Intersection eachInter,
                                    List<RoadSection> roads,
                                    List<Intersection> Network
                                )
        {
            int nID = eachInter.GetID();

            // The left and right node must be handle.
            Boolean bIsLeftNode = IsLeftNode(nID);
            Boolean bIsRightNode = IsRightNode(nID);


            int nNetworkMode = 10;

            if (true == bIsLeftNode)
            {
                // Up
                int nUp = nID - nNetworkMode;
                HandleFourDirections(eachInter, roads, Network, nUp);

                // Down
                int nDown = nID + nNetworkMode;
                HandleFourDirections(eachInter, roads, Network, nDown);

                // Right
                int nRight = nID + 1;
                HandleFourDirections(eachInter, roads, Network, nRight);
            }
            else if (true == bIsRightNode)
            {
                // Up
                int nUp = nID - nNetworkMode;
                HandleFourDirections(eachInter, roads, Network, nUp);

                // Left 
                int nLeft = nID - 1;
                HandleFourDirections(eachInter, roads, Network, nLeft);

                // Down
                int nDown = nID + nNetworkMode;
                HandleFourDirections(eachInter, roads, Network, nDown);
            }
            else
            {
                // Up
                int nUp = nID - nNetworkMode;
                HandleFourDirections(eachInter, roads, Network, nUp);

                // Left 
                int nLeft = nID - 1;
                HandleFourDirections(eachInter, roads, Network, nLeft);

                // Down
                int nDown = nID + nNetworkMode;
                HandleFourDirections(eachInter, roads, Network, nDown);

                // Right
                int nRight = nID + 1;
                HandleFourDirections(eachInter, roads, Network, nRight);
            }

        }

        private bool IsRightNode(int nID)
        {
            Boolean bRtn = false;

            if (0 == nID % 10)
            {
                bRtn = true;
            }


            return bRtn;
        }

        private bool IsLeftNode(int nID)
        {
            Boolean bRtn = false;

            int nNum = nID - 1;
            if (0 == nNum % 10)
            {
                bRtn = true;
            }

            return bRtn;
        }

        private void HandleFourDirections(Intersection eachInter, List<RoadSection> roads, List<Intersection> Network, int nDirection)
        {
            Intersection interDirection = FindIntersection(nDirection, Network);
            // If the inter is exist, then there must be a road.
            if (null != interDirection)
            {
                List<RoadSection> outList = eachInter.GetOutgoings();
                // Outgoing.
                HandleTwoNodes(eachInter, interDirection, roads, outList);


                List<RoadSection> incomeList = eachInter.GetIncoming();
                // Incoming
                HandleTwoNodes(interDirection, eachInter, roads, incomeList);
            }
        }

        // Handle Two Nodes.
        // Produce roads.
        // Set roads of node.
        private void HandleTwoNodes(
                                    Intersection start,
                                    Intersection end,
                                    List<RoadSection> roads,
                                    List<RoadSection> List
                                    )
        {
            // Get road name.
            String strRoadName = ComposeRoadName(start, end);

            // Find it in the roads.
            // If the road has not been new, then new it.
            RoadSection roadFind = FindRoadInList(strRoadName, roads);
            if (null == roadFind)
            {
                roadFind = new RoadSection(strRoadName);
                roadFind.SetNodes(start, end);
                roads.Add(roadFind);
            }

            // Add to the list.
            List.Add(roadFind);

        }

        private RoadSection FindRoadInList(string strRoadName, List<RoadSection> roads)
        {
            RoadSection roadRtn = null;

            int nSize = roads.Count;
            for (int i = 0; i < nSize; i++)
            {
                RoadSection eachRoad = roads[i];
                String strEachRoad = eachRoad.GetName();
                if (0 == string.Compare(strRoadName, strEachRoad))
                {
                    roadRtn = eachRoad;
                    break;
                }
            }

            return roadRtn;
        }

        private Intersection FindIntersection(int nID, List<Intersection> Network)
        {
            Intersection interRtn = null;

            int nSize = Network.Count;
            for (int i = 0; i < nSize; i++)
            {
                Intersection eachInter = Network[i];
                if (nID == eachInter.GetID())
                {
                    interRtn = eachInter;
                    break;
                }
            }


            return interRtn;
        }

        private SingleODIntersection FindIntersection(int nID, List<SingleODIntersection> Network)
        {
            SingleODIntersection interRtn = null;

            int nSize = Network.Count;
            for (int i = 0; i < nSize; i++)
            {
                SingleODIntersection eachInter = Network[i];
                if (nID == eachInter.GetID())
                {
                    interRtn = eachInter;
                    break;
                }
            }

            return interRtn;
        }

        private string ComposeRoadName(Intersection start, Intersection end)
        {
            String strRtn = null;

            strRtn = String.Format("{0}{1}", start.GetName(), end.GetName());

            return strRtn;
        }

        private string GetInterID(int i)
        {
            String strRtn = null;

            strRtn = String.Format("N{0}", i);

            return strRtn;
        }



        #endregion

        #region Q Method without BD Part.

        private void Qmethod(List<Intersection> NetworkIntersections, List<RoadSection> NetworkRoads)
        {
            // Initial Network environment.
            // SingleODNetwork.
            SingleODNetwork singleNet = QInitalNetwork(NetworkIntersections, NetworkRoads);



            // Start N13    Destination N88
            int OriginNode = 13;
            int DestiantionNode = 88;

            // Initialization.
            Initialization(singleNet, DestiantionNode);

            // Iteration.
            Iteration(singleNet, DestiantionNode);


            // Could fine a route from Start to Destination.
            SingleODRoute route = FindRoute(OriginNode, DestiantionNode, singleNet);


            // OutputRoute
            OutputRoute(route);

            Console.WriteLine("It can Find Route");
        }

        private void OutputRoute(SingleODRoute route)
        {
            List<SingleODIntersection> listInter = route.GetInterList();

            int iInterSize = listInter.Count;
            for (int i = 0; i < iInterSize; i++)
            {
                SingleODIntersection inter = listInter[i];

                String strOutput = inter.GetName();

                Console.Write("{0}, ", strOutput);
            }
        }

        private SingleODRoute FindRoute(int OriginNode, int DestiantionNode, SingleODNetwork singleNet)
        {
            SingleODRoute route = new SingleODRoute();

            List<SingleODIntersection> routeInterList = route.GetInterList();
            List<SingleODRoad> routeRoadList = route.GetRoadList();

            List<SingleODIntersection> list = singleNet.GetIntersectionList();

            // Start from Origin Node.

            // End at Destination Node.


            SingleODIntersection StartNode = FindIntersection(OriginNode, list);
            routeInterList.Add(StartNode);

            int iCurNode = OriginNode;

            while (iCurNode != DestiantionNode)
            {

                SingleODIntersection curNode = FindIntersection(iCurNode, list);

                // Get road with the min Q value
                SingleODRoad curRoad = GetRoadWithMinQ(curNode);

                // Add to route.
                routeRoadList.Add(curRoad);

                // Get next Node.
                curNode = curRoad.GetEndNode();

                // Add cur to route.
                routeInterList.Add(curNode);

                // Get the iCurNode.
                iCurNode = curNode.GetID();
            }


            return route;
        }

        private SingleODRoad GetRoadWithMinQ(SingleODIntersection curNode)
        {
            SingleODRoad road = null;

            double dMinValue = GetMinQvalue(curNode);
            road = GetRoadWithMinQ(dMinValue, curNode);

            return road;
        }

        private SingleODRoad GetRoadWithMinQ(double dMinValue, SingleODIntersection interOut)
        {
            SingleODRoad road = null;

            List<SingleODRoad> list = interOut.GetOutgoings();
            int nRoadSize = list.Count;
            for (int i = 0; i < nRoadSize; i++)
            {
                SingleODRoad eachRoad = list[i];
                double dQvalue = eachRoad.GetQValue();

                if (dQvalue == dMinValue)
                {
                    road = eachRoad;
                    break;
                }
            }


            return road;
        }

        // If the start node is the destination node.
        private Boolean IsStartFromDesRoad(SingleODRoad eachRoad, int DestiantionNode)
        {
            Boolean bRtn = false;

            SingleODIntersection inter = eachRoad.GetStartNode();
            int nRoadStart = inter.GetID();

            if (nRoadStart == DestiantionNode)
            {
                bRtn = true;
            }

            return bRtn;
        }

        private void Iteration(SingleODNetwork singleNet, int DestiantionNode)
        {
            Boolean bStop = false;
            while (false == bStop)
            {
                // First consider it converge.
                bStop = true;


                // Find if some value has been updated, 
                // then set bStop = false;
                Boolean bUpdate = UpdateNetwork(singleNet, DestiantionNode);
                if (true == bUpdate)
                {
                    bStop = false;
                }

            }

            // Output All the Q value of roads.
            // OutputInformation(singleNet);

            // Console.WriteLine("It can converge!");
        }

        private void OutputInformation(SingleODNetwork singleNet)
        {
            List<SingleODRoad> list = singleNet.GetRoadList();

            int nRoadSize = list.Count;
            for (int i = 0; i < nRoadSize; i++)
            {
                SingleODRoad road = list[i];

                // Start End Qvalue TravelTime
                String strStart = road.GetStartNode().GetName();
                String strEnd = road.GetEndNode().GetName();
                String strQvalue = road.GetQValue().ToString();
                String strTravelTime = road.GetTravelTime().ToString();

                String strOutput = string.Format("{0,-4} {1,-4} {2,-30}{3,-20}", strStart, strEnd, strQvalue, strTravelTime);
                Console.WriteLine(strOutput);
            }
        }

        // Update the whole network.
        // If something has been updated, return true.
        private bool UpdateNetwork(SingleODNetwork singleNet, int DestiantionNode)
        {
            Boolean bRtn = false;

            // Update Q value through whole network using roads.
            List<SingleODRoad> list = singleNet.GetRoadList();

            int nNum = list.Count;

            // Roads.
            for (int i = 0; i < nNum; i++)
            {
                SingleODRoad eachRoad = list[i];
                Boolean bIsDestination = IsStartFromDesRoad(eachRoad, DestiantionNode);
                if (true == bIsDestination)
                {
                    continue;
                }

                Boolean bIsConnetDes = IsConnectDes(eachRoad, DestiantionNode);
                if (true == bIsConnetDes)
                {
                    continue;
                }

                Boolean bUpdate = UpdateQvalueOfInter(eachRoad);

                if (true == bUpdate)
                {
                    bRtn = true;
                }
            }

            return bRtn;
        }

        private bool UpdateQvalueOfInter(SingleODRoad eachRoad)
        {
            Boolean bRtn = false;

            Boolean bRoadUpdate = UpdateQvalueOfRoad(eachRoad);

            if (true == bRoadUpdate)
            {
                bRtn = true;
            }

            return bRtn;
        }

        private bool UpdateQvalueOfRoad(SingleODRoad eachRoad)
        {
            Boolean bRtn = false;

            // Get travel time.
            double dTravelTime = eachRoad.GetTravelTime();

            // Get min next Q value.
            SingleODIntersection end = eachRoad.GetEndNode();
            double dMinQvalue = GetMinQvalue(end);

            // Get the current Q
            double dCurrentQ = eachRoad.GetQValue();

            // Compare to decide if need to update.
            double dNewQ = dTravelTime + dMinQvalue;

            if (dCurrentQ != dNewQ)
            {
                // 
                eachRoad.SetQValue(dNewQ);
                bRtn = true;
            }



            return bRtn;
        }

        // Get the min Q value of roads.
        private double GetMinQvalue(SingleODIntersection interOut)
        {
            double dRtn = double.MaxValue;

            List<SingleODRoad> list = interOut.GetOutgoings();
            int nRoadSize = list.Count;
            for (int i = 0; i < nRoadSize; i++)
            {
                SingleODRoad eachRoad = list[i];
                double dQvalue = eachRoad.GetQValue();

                if (dQvalue < dRtn)
                {
                    dRtn = dQvalue;
                }
            }

            return dRtn;
        }

        private bool IsConnectDes(SingleODRoad road, int DestiantionNode)
        {
            Boolean bRtn = false;


            SingleODIntersection eachEndInter = road.GetEndNode();
            int nEachEndInter = eachEndInter.GetID();

            if (nEachEndInter == DestiantionNode)
            {
                bRtn = true;

            }

            return bRtn;
        }

        private bool IsDestinationInter(SingleODIntersection eachInter, int DestiantionNode)
        {
            Boolean bRtn = false;

            int nEachInter = eachInter.GetID();
            if (nEachInter == DestiantionNode)
            {
                bRtn = true;
            }

            return bRtn;
        }

        private void Initialization(SingleODNetwork singleNet, int DestiantionNode)
        {
            List<SingleODRoad> roadList = singleNet.GetRoadList();
            int nRoadsSize = roadList.Count;

            for (int i = 0; i < nRoadsSize; i++)
            {
                SingleODRoad eachRoad = roadList[i];

                // Check if the road's start node is destination.
                Boolean bIsDestinationRoad = IsStartFromDesRoad(eachRoad, DestiantionNode);
                Boolean bIsgotoDestination = IsGotoDestination(eachRoad, DestiantionNode);

                // Set roads from Destination.
                if (true == bIsDestinationRoad)
                {
                    eachRoad.SetQValue(0.0);
                }
                else if (true == bIsgotoDestination)
                {
                    double dTravlTime = eachRoad.GetTravelTime();
                    eachRoad.SetQValue(dTravlTime);
                }
                else
                {
                    // Set other roads.
                    eachRoad.SetQValue(double.MaxValue);
                }
            }
        }

        private bool IsGotoDestination(SingleODRoad eachRoad, int DestiantionNode)
        {
            Boolean bRtn = false;

            SingleODIntersection inter = eachRoad.GetEndNode();
            int nRoadEnd = inter.GetID();

            if (nRoadEnd == DestiantionNode)
            {
                bRtn = true;
            }

            return bRtn;
        }

        private SingleODNetwork QInitalNetwork(List<Intersection> NetworkIntersection, List<RoadSection> NetworkRoads)
        {
            // Build this new network.
            SingleODNetwork singleRtn = new SingleODNetwork();

            // Build up Intersection.           
            List<SingleODIntersection> InterSectionList = singleRtn.GetIntersectionList();
            InitialIntersection(InterSectionList, NetworkIntersection);

            // Build up Roads.
            List<SingleODRoad> RoadList = singleRtn.GetRoadList();
            InitialRoads(RoadList, NetworkRoads, InterSectionList);

            // Relate the intersections and roads.


            return singleRtn;
        }

        private void InitialRoads(List<SingleODRoad> RoadList, List<RoadSection> NetworkRoads, List<SingleODIntersection> InterSectionList)
        {
            int nRealRoadSize = NetworkRoads.Count;
            for (int i = 0; i < nRealRoadSize; i++)
            {
                RoadSection eachRoad = NetworkRoads[i];

                // Here we get the related information between intersection and road.

                // Get start node of road in SingleOD.
                Intersection roadStart = eachRoad.GetStartNode();
                int nStart = roadStart.GetID();
                SingleODIntersection singleStart = FindIntersection(nStart, InterSectionList);


                // Get end node of road in SingleOD.
                Intersection roadEnd = eachRoad.GetEndNode();
                int nEnd = roadEnd.GetID();
                SingleODIntersection singleEnd = FindIntersection(nEnd, InterSectionList);


                // Set Road.
                SingleODRoad sEachRoad = new SingleODRoad(eachRoad.GetName());
                sEachRoad.SetNodes(singleStart, singleEnd);
                sEachRoad.SetTravelTime(eachRoad.GetTravelTime());

                // Set incoming of node.
                List<SingleODRoad> inList = singleEnd.GetIncoming();
                inList.Add(sEachRoad);

                // Set outgoing of node.
                List<SingleODRoad> outList = singleStart.GetOutgoings();
                outList.Add(sEachRoad);


                RoadList.Add(sEachRoad);
            }
        }

        private void InitialIntersection(List<SingleODIntersection> InterSectionList, List<Intersection> Network)
        {
            int nSize = Network.Count;
            for (int i = 0; i < nSize; i++)
            {
                Intersection eachInter = Network[i];

                SingleODIntersection sEachInter = new SingleODIntersection(eachInter.GetName(), eachInter.GetID());

                InterSectionList.Add(sEachInter);
            }
        }


        #endregion

        public void Run()
        {

            // Get the Map data.
            GetMapData(NetworkIntersections, NetworkRoads);

            // Conventional Q method.
            Qmethod(NetworkIntersections, NetworkRoads);

            // Mr Xu.

            // Mr Yu.

        }





    }
}
